␈↓ β+ENUMERATION OF THE GRAPHS OF MOLECULES

␈↓␈↓ ¬ELarry Masinter
␈↓ ∧kComputer Science Department
␈↓ ¬*Stanford University
␈↓ ¬*Stanford, California

␈↓ ¬←May, 1973






␈↓␈↓ α(ABSTRACT.␈α∪Previously,␈α∩enumerations␈α∪of␈α∩the␈α∪number␈α∩of␈α∪equialence␈α∪classes␈α∩of
␈↓ α(graphs␈αwith␈αa␈αgiven␈αpartitions␈αhave␈αbeen␈αgiven␈↓#
1␈↓#␈↓#
,␈↓#␈↓#
2␈↓#.␈α These␈αresults␈αare␈αextended␈αto
␈↓␈↓ α(give␈αenumerations␈αfor␈αthe␈αnumber␈αof␈αequivalence␈αclasses␈αof␈αconnected␈αmultigraphs.
␈↓ α(Connected␈α∀multigraphs␈α∀correspond␈α∀directly␈α∀with␈α∀chemical␈α∀molecules;␈α∃thus␈α∀the
␈↓ α(enumeration␈αcan␈αbe␈αapplied␈αto␈αcount␈αthe␈αnumber␈αof␈αchemical␈αisomers␈αconstructable
␈↓ α(from␈α
a␈αgiven␈α
set␈αof␈α
atoms.␈α
 Bounds␈αmay␈α
be␈αplaced␈α
on␈α
the␈αmultiplicity␈α
of␈αeach␈α
edge,
␈↓ α(corrsponding␈α
to␈α
restrictions␈α
on␈α
multiple␈α
bonds␈α
in␈α
chemical␈α
structures.























------------------
␈↓#
1␈↓#PARTHASARATHY␈α
PAPER

␈↓#
2␈↓#OTHER␈α
REFERENCE



␈↓␈↓αINTRODUCTION␈↓


␈↓␈↓αDEFINITIONS␈↓

␈↓␈↓αDefinition.␈↓␈α∞A␈α∂␈↓↓multi-graph␈↓␈α∞of␈α∂order␈α∞␈↓βn␈↓␈α∞is␈α∂the␈α∞set␈α∂␈↓βN={1,...,n}␈↓␈α∞(called␈α∞the␈α∂␈↓↓nodes␈↓␈α∞of␈α∂the␈α∞graph)

together␈α∂with␈α∂a␈α∂mapping␈α∂␈↓βf␈↓␈α∂from␈α∂the␈α∂set␈α∂␈↓βE(n)={{i,j}|1≤i<j≤n}␈↓␈α∂to␈α∂the␈α∂set␈α⊂of␈α∂non-negative

integers␈α␈↓βI␈↓#
+␈↓#␈↓.␈α
 Those␈α␈↓βeεE␈↓␈α
for␈αwhich␈α␈↓βf(e)≠0␈↓␈α
are␈αsaid␈α
to␈αbe␈α␈↓↓edges␈↓␈α
of␈αthe␈α
graph;␈αthe␈α␈↓↓multiplicity␈↓␈α
of

␈↓βe␈↓␈α∞is␈α∂␈↓βf(e)␈↓.␈α∞ Also,␈α∞if␈α∂␈↓βe={i,j}␈↓␈α∞then␈α∞node␈α∂␈↓βi␈↓␈α∞is␈α∞said␈α∂to␈α∞be␈α∞connected␈α∂to␈α∞node␈α∞␈↓βj␈↓␈α∂with␈α∞multiplicity

␈↓βf({i,j})␈↓.␈α Multigraphs␈αmay␈αbe␈αrestricted␈αto␈αthose␈αwhose␈αedges␈αhave␈αmaximum␈αmultiplicity␈α␈↓βk␈↓␈αby

restricting␈α
the␈α
range␈α
of␈α
␈↓βf␈↓␈αto␈α
be␈α
the␈α
set␈α
of␈αintegers␈α
␈↓β{0,1,...,k}␈↓.␈α
 A␈α
␈↓↓k-multigraph␈↓␈α
is␈α
thus␈αan

element␈α
of␈α
␈↓βk+1␈↓#
E(n)␈↓#␈↓.



␈↓The␈α∞␈↓↓degree␈↓␈α∞of␈α∞a␈α∞node␈α∞␈↓βnεN␈↓␈α∞is␈α∞␈↓βd(n)=␈↓#vm≠n␈↓#f({n,m})␈↓.␈α∞ The␈α∞degree␈α∞is␈α∞the␈α∞total␈α∞number␈α∞of␈α∞other

nodes␈α⊂␈↓βn␈↓␈α⊂is␈α⊂connected␈α⊂to,␈α⊂with␈α⊃each␈α⊂connection␈α⊂counted␈α⊂the␈α⊂appropriate␈α⊂multiplicity␈α⊃number␈α⊂of

times.



␈↓αDefinition.␈↓␈α≡The␈α≡␈↓↓degree␈α≡seqence␈↓␈α≥of␈α≡a␈α≡graph␈α≡␈↓βf␈↓␈α≡is␈α≥defined␈α≡to␈α≡be␈α≡the␈α≡ordered␈α≥list

␈↓βds(f)=(o␈↓#v1␈↓#,o␈↓#v2␈↓#,...)␈↓,␈α∃where␈α∃␈↓βo␈↓#v1␈↓#≤o␈↓#v2␈↓#≤...≤o␈↓#vn␈↓#␈↓,␈α∃and␈α∃␈↓β|{j:o␈↓#vj␈↓#=k}|=|{l:d(l)=k}|␈↓.␈α∃ It␈α∃is␈α∃the

sorted␈α
list␈α
of␈α
the␈α
degrees␈α
of␈α
the␈α
nodes␈α
of␈α
␈↓βf␈↓.



␈↓αDefinition.␈↓␈α⊃Given␈α⊃a␈α⊂set␈α⊃␈↓βX␈↓,␈α⊃the␈α⊃␈↓↓symmetry␈α⊂group␈↓␈α⊃on␈α⊃␈↓βX␈↓,␈α⊃or␈α⊂␈↓βS␈↓#vX␈↓#␈↓,␈α⊃is␈α⊃defined␈α⊃to␈α⊂be␈α⊃the␈α⊃set␈α⊃of␈α⊂all

automorphisms␈α
from␈α
␈↓βX␈↓␈α
onto␈α
␈↓βX␈↓.



␈↓αDefinition.␈↓␈αTwo␈αgraphs␈α
␈↓βf␈↓,␈α␈↓βg␈↓␈αof␈α
order␈α␈↓βn␈↓␈αare␈αsaid␈α
to␈αbe␈α␈↓βisomorphic␈↓␈α
if␈αthere␈αexists␈α
a␈αpermutation

␈↓βαεS␈↓#vN␈↓#␈↓␈αsuch␈αthat␈α␈↓β∀i,jεN␈α
f({i,j})=g({α(i),α(j)})␈↓.␈α This␈αis␈αwritten␈α
␈↓βf↔g␈↓.



␈↓αLemma.␈↓␈α
f␈↓β↔␈↓g␈α
=>␈α
ds(f)␈α
=␈α
ds(g).


␈↓␈↓ ε_1␈↓ 
x



␈↓αDefinition.␈↓␈α
Given␈α
a␈α
set␈α
␈↓βF␈↓␈α
and␈α
an␈α
equivalence␈α
relation␈α
␈↓β↔␈↓␈α
on␈α
␈↓βF␈↓,␈α
we␈α
define␈α
the␈α
set␈α
of␈αequivalence␈α
classes

␈↓of␈α␈↓βF␈↓␈αunder␈α␈↓β↔␈↓,␈α␈↓βF␈↓/␈↓β↔␈↓,␈αto␈αbe␈α␈↓β{{fεF:f↔g}␈α|␈αgεF}␈↓.


␈↓αSTATEMENT OF PROBLEM␈↓

␈↓Thus,␈αthe␈α
the␈αproblem␈αis␈α
to␈αfind␈αa␈α
generating␈αfunction␈αfor␈α
the␈αnumber␈αof␈α
equivalence␈αclasses␈αof␈α
k-

multigraphs␈α
with␈α
a␈α
given␈α
degree␈α
sequence␈α
␈↓β(o␈↓#v0␈↓#,o␈↓#v1␈↓#,o␈↓#v2␈↓#,...)␈↓.


␈↓␈↓αBurnside lemma␈↓

␈↓Given␈αa␈αset␈α␈↓βE␈↓,␈αand␈αa␈αgroup␈α␈↓βG␈↓,␈αa␈αmapping␈α␈↓β%:G→S␈↓#vE␈↓#␈↓,␈αa␈αset␈α␈↓βB␈↓,␈αand␈α␈↓β#=B␈↓#
E␈↓#␈↓;␈αand␈αthe␈αequivalence␈αrelation

for␈α␈↓βf,gε#,␈αf↔g␈↓␈α
if␈αthere␈αexists␈α
␈↓βαεG␈↓␈αsuch␈αthat␈α
␈↓βf=g⊗%(α)␈↓.



␈↓Given␈αa␈αweight␈αfunction␈α␈↓βw:#→@␈↓,␈αwhere␈α␈↓β@␈↓␈α
is␈αa␈αfield,␈αsuch␈αthat␈α␈↓βf↔g␈α=>␈α
w(f)=w(g)␈↓.



For␈α
␈↓βF␈↓␈α
an␈α
equivalence␈α
class␈α
in␈α
␈↓β#␈↓/␈↓β↔␈↓,␈α
define␈α
␈↓βW(F)␈↓␈α
to␈α
be␈α
␈↓βw(f)␈↓␈α
for␈α
any␈α
␈↓βfεF␈↓.␈α
 Then



␈↓β␈↓#vFε#/↔␈↓#W(F)␈α⊂=␈α⊂␈↓#
␈α⊂1␈α⊂␈↓#  ␈↓#  ␈↓#␈↓#vf=f⊗%α␈↓#w(f).␈↓
          ␈↓#v|G|
          -␈αα-␈↓#vαεG



To␈αapply␈α
the␈αBernside␈αlemma␈α
to␈αthis␈αproblem,␈α
it␈αis␈αnecessary␈α
to␈αdevise␈αa␈α
weight␈αfunction␈αsuch␈α
that

two␈αgraphs␈αwith␈αthe␈αsame␈αdegree␈αsequence␈αhave␈αthe␈αsame␈αweight␈αand␈αgraphs␈αwith␈αdifferent␈α
degree

sequences␈α
have␈α
different␈αweights.␈α
Further,␈α
to␈αconstruct␈α
a␈α
generating␈αfunction␈α
for␈α
the␈α
number␈αof

graphs␈αwith␈αgiven␈αdegree␈α
sequences,␈αthe␈αdegree␈αsequences␈αshould␈α
be␈αreflected␈αin␈αthe␈α
exponents␈αof

terms␈α
in␈α
the␈α
weight␈α
rather␈α
than␈α
in␈α
the␈α
coefficient.



Thus,␈α⊗we␈α⊗define␈α⊗the␈α⊗weight␈α⊗function␈α⊗␈↓βw␈↓#vo␈↓#␈↓␈α⊗on␈α⊗␈↓βk␈↓#
E(n)␈↓#␈↓␈α⊗into␈α⊗the␈α⊗set␈α⊗of␈α⊗real␈α⊗polynomials␈α∃in

␈↓βu␈↓#v1␈↓#,u␈↓#v2␈↓#,...,u␈↓#vn␈↓#␈↓␈α
by:



␈↓βw␈↓#vo␈↓#(f)=π␈↓#v1≤i<j≤n␈↓#(u␈↓#vi␈↓#u␈↓#vj␈↓#)␈↓#
f({i,j})␈↓#␈↓

␈↓ ε_2␈↓ 
x



The␈αexponent␈α
of␈α␈↓βu␈↓#vi␈↓#␈↓␈α
in␈α␈↓βw␈↓#vo␈↓#(f)␈↓␈α
will␈αbe␈α
the␈αdegree␈α
of␈αnode␈α
␈↓βi␈↓␈αin␈α
the␈αgraph␈α
␈↓β(N,f)␈↓.␈α Unfortunately,

␈↓β␈↓βds(f)=ds(g)␈↓␈α⊂(or␈α∂even␈α⊂␈↓βf↔g␈↓)␈α⊂does␈α∂not␈α⊂imply␈α⊂␈↓βw␈↓#vo␈↓#(f)=w␈↓#vo␈↓#(g)␈↓;␈α∂although␈α⊂␈↓βf␈↓␈α⊂and␈α∂␈↓βg␈↓␈α⊂have␈α⊂the␈α∂same

degree␈α⊃sequence,␈α⊃the␈α⊃exponents␈α⊃may␈α⊃be␈α⊃permuted␈α∩among␈α⊃the␈α⊃␈↓βu␈↓#vi␈↓#␈↓.␈α⊃ It␈α⊃is␈α⊃necessary␈α⊃to␈α∩apply␈α⊃a

symmetrizing␈α
operator␈α
␈↓β∂␈↓:



␈↓αDefinition.␈↓␈αFor␈α␈↓βw␈↓␈αa␈αfunction␈αin␈α␈↓βu␈↓#v1␈↓#,␈αu␈↓#v2␈↓#,␈α...␈αu␈↓#vn␈↓#,␈↓␈αdefine

␈↓β∂(w)(u␈↓#v1␈↓#,u␈↓#v2␈↓#,...,u␈↓#vn␈↓#)=␈↓#
1 ␈↓#␈↓#    ␈↓#vN␈↓#]w(u␈↓#vα␈↓#l1␈↓#v␈↓#,u␈↓#vα␈↓#l2␈↓#v␈↓#,...,u␈↓#vα␈↓#ln␈↓#v␈↓#)␈↓
                   ␈↓#vn!
                   --[αεS

Note:
        1) ␈↓β∂␈↓ is linear
        2) if ␈↓βw␈↓ is symmetric, then ␈↓β∂w=w␈↓;
           specifically, ␈↓β∂∂w=∂w␈↓ for any ␈↓βw␈↓.

The weight function w can now be defined by:
        for ␈↓βfεk␈↓#
E␈↓#,  w(f)=∂w␈↓#vo␈↓#(f)␈↓.



␈↓This␈αweight␈αfunction␈αsatisfies␈α
our␈αrequirements:␈αIf␈αthe␈α
degree␈αsequence␈αof␈α␈↓βf␈↓␈αis␈α
␈↓βo␈↓#v1␈↓#≤o␈↓#v2␈↓#≤o␈↓#v3␈↓#≤...o␈↓#vn␈↓#␈↓,

the␈α
weight␈α
of␈α
␈↓βf␈↓␈α
will␈α
be:

                ␈↓β∂u␈↓#v1␈↓# ␈↓#u␈↓#v2␈↓# ␈↓#...u␈↓#vn␈↓# ␈↓#␈↓
                  ␈↓#
o1 ␈↓#
o2    ␈↓#
on



␈↓Then,␈α
using␈α
the␈α
definition␈α
of␈α
␈↓β↔␈↓␈α
given␈α
earlier,␈α
with␈α
the␈α
representation␈α
of␈α
the␈α
group␈α
␈↓βG=S␈↓#vN␈↓#␈↓␈α
by:



␈↓αDefinition.␈↓␈α∞␈↓β%:S␈↓#vN␈↓#→S␈↓#vE␈↓#␈α∞by␈α∞%(β){i,j}={β(i),β(j)}␈↓



we␈α
obtain:
␈↓β␈↓#vfε#/↔␈↓#w(f)=␈↓#vn!␈↓#␈↓#␈↓#vαεS␈↓#ln␈↓#v␈↓#␈↓#vf=f⊗%α␈↓#w(f)
          ␈↓#
1 
          --
        =␈↓#vn!␈↓#␈↓#  ␈↓#vαεS␈↓#ln␈↓#v␈↓#␈↓#vf=f⊗%α␈↓#w␈↓#vo␈↓#(f)␈↓
         ␈↓#
1 
         -- ∂



␈↓Consider␈α␈↓β␈↓#vf=f⊗%α␈↓#w␈↓#vo␈↓#(f)␈↓␈αand␈α
the␈αcycles␈αof␈α
␈↓β%␈↓α.␈α ␈↓βf=f⊗%α␈α<=>␈α
f␈↓␈αis␈αconstant␈α
on␈αeach␈αcycle␈α
of␈α␈↓β%␈↓α.

For␈α
a␈α
given␈α
α,␈α
let␈α
␈↓βM␈↓#v≡␈↓#␈↓␈α
be␈αthe␈α
number␈α
of␈α
cycles␈α
of␈α
␈↓β%␈↓α;␈α
for␈α␈↓β1≤r≤M␈↓#v≡␈↓#␈↓,␈α
let␈α
␈↓βC␈↓#vr␈↓#␈↓#␈↓␈α
be␈α
the␈α
set␈α
of␈αedges
                                                      ␈↓#
≡

(elements␈α
of␈α
␈↓βE␈↓)␈α
in␈α
the␈α
r-th␈α
cycle␈α
of␈α
␈↓β%␈↓α,␈α
and

␈↓ ε_3␈↓ 
x



␈↓␈↓βU␈↓#
≡␈↓#&␈↓#vr␈↓#=π␈↓#v{l,p}εC␈↓#lr␈↓#v␈↓#u␈↓#vl␈↓#u␈↓#vp␈↓#␈↓

Then for ␈↓βf=f⊗%α␈↓,

␈↓βw␈↓#vo␈↓#(f)=π␈↓#vi,j␈↓#(u␈↓#vi␈↓#u␈↓#vj␈↓#)␈↓#
f({i,j})␈↓#

     =π␈↓#v1≤r≤M␈↓#(U␈↓#vr␈↓#␈↓#)␈↓#
f(cycle r)␈↓#␈↓
              ␈↓#
≡



␈↓Since␈α
each␈α␈↓βf=f⊗%α␈↓␈α
can␈α
be␈αspecified␈α
by␈αits␈α
value␈α
on␈αthe␈α
cycles␈αof␈α
␈↓β%␈↓α,␈α
there␈αis␈α
a␈α1-1␈α
correspondence

between␈α⊂such␈α⊃␈↓βf␈↓␈α⊂and␈α⊃␈↓β∨ε{0,1,...,k}␈↓#
M␈↓#␈↓,␈α⊂where␈α⊃␈↓βk␈↓␈α⊂is␈α⊂the␈α⊃maximum␈α⊂multiplicity␈α⊃(can␈α⊂be␈α⊃∞),␈α⊂by

␈↓β∨(r)=f(cycle␈αr).␈↓␈αIn␈αparticular,

  ␈↓βV(α)=␈↓#vf=f⊗%α␈↓#w␈↓#vo␈↓#(f) =␈↓#v∨␈↓# π␈↓#v1≤r≤Mα␈↓# (U␈↓#vr␈↓#␈↓#)␈↓#
∨(r)␈↓#␈↓
                                ␈↓#
≡
        =␈↓βπ␈↓␈↓#v1≤r≤Mα␈↓#␈↓#
1-(U␈↓#r␈↓#
)␈↓#∀k␈↓#
␈↓#
                ␈↓#v1 - U␈↓#lr␈↓#v␈↓#
                -------
      (or ␈↓βπ␈↓␈↓#v1≤rMα␈↓#␈↓#
  1  ␈↓#
                ␈↓#v1-U␈↓#lr␈↓#v␈↓#
                ------- if k=∞)



␈↓Our␈αgenerating␈αfunction␈αis␈αnow␈α␈↓β␈↓#vn!␈↓# ␈↓#vαεS␈↓#lN␈↓#v␈↓#V(α).␈↓␈αWe␈αwish␈αto␈αgroup␈αthe␈αsummation␈αby␈αthose
                          ␈↓#
1␈α␈↓#
                          --∂

permutations␈α
α␈α
with␈α
cycle␈α
index␈α
␈↓βλ␈↓#v1␈↓#+2λ␈↓#v2␈↓#+...+nλ␈↓#vn␈↓#=n␈↓␈α
(␈↓βλ␈↓#vi␈↓#␈↓␈α
is␈α
the␈α
number␈α
of␈α
␈↓βi␈↓-cycles␈α
of␈α
α;␈αnote

that␈αthis␈αis␈αdifferent␈αfrom␈αthe␈αnumber␈αof␈αvarious␈αcycles␈αof␈α␈↓β%␈↓α).␈α Let␈α␈↓βα⊗(λ␈↓#v1␈↓#,λ␈↓#v2␈↓#,...,λ␈↓#vn␈↓#)␈↓␈αbe␈αthe

permutation␈α
obtained␈α
by␈α
filling␈α
in␈α
the␈α
integers␈α
␈↓β1,...,n␈↓␈α
into␈α
the␈α
slots␈α
in

  (.)(.)...(.) (..)(..)(..) ... (.. ...)
   ----------   ----------       -----
   λ␈↓#v1␈↓# 1-cycles  λ␈↓#v2␈↓# 2-cycles ... λ␈↓#vn␈↓# n-cycles



␈↓For␈α≠␈↓β∨εS␈↓#vN␈↓#,␈α≠∨α⊗∨␈↓#
-1␈↓#␈↓␈α~has␈α≠the␈α≠same␈α~cycle␈α≠structure␈α≠as␈α~α␈↓β⊗␈↓;␈α≠further,␈α≠there␈α≠are␈α~exactly

␈↓βY(λ␈↓#v1␈↓#,λ␈↓#v2␈↓#,...,λ␈↓#vn␈↓#)=π␈↓#v1≤k≤n␈↓#␈α(k␈↓#
␈↓#∀≡␈↓#
␈↓↓␈↓#
k␈↓#λ␈↓#vk␈↓#!)␈↓␈αsuch␈αpermutations.



Thus,



␈↓β␈↓#vαεS␈↓#lN␈↓#v␈↓#V(α)␈α=␈↓#vλ␈↓#l1␈↓#v+...+λ␈↓#ln␈↓#v=n␈↓#␈↓#vY(␈↓↓␈↓#v)␈↓#␈↓#  ␈α␈↓β␈↓↓␈↓#v␈↓β␈↓#v∨␈↓↓␈↓#vεS␈↓#lN␈↓#v␈↓#V(␈↓β∨␈↓↓α␈↓β⊗␈↓↓&␈↓#v≡␈↓#␈↓β∨␈↓↓␈↓#
-1␈↓#)␈↓
                    ␈↓#
␈α 1␈α 
                    -----





␈↓ ε_4␈↓ 
x